/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 * 输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
 */
var combinationSum = function (candidates, target) {
  //   const sortAr = candidates.sort((a, b) => a - b)
  const resArr = []
  //   let right = sortAr.length - 1
  const getData = (num, left, arr) => {
    if (candidates[left] === num) {
      if (left > 0) {
        getData(num, left - 1, [...arr])
      }
      arr.push(candidates[left])
      resArr.push(arr)

      return -1
    } else {
      // 如果当前值比目标值小， 继续减
      // 如果剪完之后的目标值比最小值要小，就没有比的必要了
      arr.push(candidates[left])
      if (num - candidates[left] >= 0) {
        getData(num - candidates[left], left, [...arr])
      }
      arr.pop()
      left > 0 && getData(num, left - 1, [...arr])
      return false
    }
  }
  getData(target, candidates.length - 1, [])
  return resArr
}
console.log(combinationSum([4, 2, 8], 8))
// console.log(combinationSum([2, 5, 1], 5))
